//! AVL 树
//!
//! 为了度量一棵二叉树的平衡，我们可以比较左右分支的高度差，如果差很大，
//! 则说明树不平衡。定义一棵树的高度差如下:
//!   δ(T) = |Tr| − |Tl|
//! 其中 |T | 代表树 T 的高度，Tl 和 Tr 分别代表左右分支。
//!
//! 如果一棵二叉搜索树的所有子树都满足如下条件，我们称之为 AVL 树。
//!   |δ(T )| ≤ 1
//!
//!
//! 结论：
//! AVL树是在1962年由Adelson-Velskii和Landis发表的。AVL树的命名来自两位作者的名字。
//! 它的历史要比红黑树更早。人们很自然会比较AVL树和红黑树。它们都是自平衡二叉搜索树，对于
//! 主要的树操作，它们的性能都是 O(lg n) 的。AVL树的平衡性更为严格，因此在频繁查询的情况下，
//! 其表现要好于红黑树。但红黑树在频繁插入和删除的情况下性能更佳。
//! 很多流行的程序库使用红黑树作为自平衡二叉搜索树的内部实现，例如STL，AVL树同样也可以直观、高效
//! 地解决平衡问题。
//!
//! 如下tree，是一棵正确的rb tree，而不是一棵正确的avl tree
//!
//! https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
//!
//! 输入序列: [100, 150, 50, 125, 114, 107]
//!
//!    B(100)
//!    /   \
//! B(50)    R(125)
//!       /    \
//!    B(114)   B(150)
//!     /
//!   R(107)
//!
//!

/*

1. ll lean (左左偏)

           (z)
          /   \
        (y)     D
       /   \
     (x)     C
    /   \
   A     B

delta(z) = -2
delta(y) = -1

2. rr lean

   (x)
  /   \
 A    (y)
      /  \
     B   (z)
         /  \
        C    D

delta(x) = 2
delta(y) = 1

3. rl lean
   (x)
  /   \
 A    (z)
      /  \
    (y)    D
   /   \
  B     C

delta(x) = 2
delta(z) = -1

4. lr lean
            (z)
           /   \
         (x)    D
        /  \
       A   (y)
           / \
          B   C

 delta(z) = -2
 delta(x) = 1

===========================================

被修复为一个统一形式

             (y)
          /      \
        (x)      (z)
       /   \     /  \
      A     B   C    D

delta(y) = 0

 */
